package weektwo;

import java.util.HashMap;
import java.util.Map;

public class LRUCache_146 {
    private class Node{
        public int key;
        public int value;
        public Node pre;
        public Node next;
    }

    private Map<Integer, Node> map;

    private Node head;
    private Node tail;
    private int capacity;

    public LRUCache_146(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.tail.pre = this.head;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node res = map.get(key);
        removeNodeFromList(res);
        addNodetoHead(res);
        return res.value;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.value = value;
            removeNodeFromList(node);
            addNodetoHead(node);
        }else{
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;
            if(map.size()>=capacity){
                map.remove(this.tail.pre.key);
                removeNodeFromList(this.tail.pre);
            }
            addNodetoHead(newNode);
            map.put(key, newNode);
        }

    }

    private void removeNodeFromList(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addNodetoHead(Node node){
        node.next = this.head.next;
        node.next.pre = node;
        this.head.next = node;
        node.pre = this.head;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
